package org.shj.suanfa.sort

object MergeSort {
  def main(args: Array[String]): Unit = {
    val arr = List(9,7, 10, 5, 3, 6, 4, 8)
    println(msort((x: Int, y: Int) => x < y)(arr))
  }
  
  def msort[T](less: (T,T) => Boolean)(xs: List[T]) : List[T] = {
    def merge(xs: List[T], ys: List[T]) : List[T] = 
      (xs, ys) match{
      case (Nil, _) => ys
      case (_, Nil) => xs
      case (x :: xs1, y :: ys1) =>
        if (less(x,y)) x :: merge(xs1,ys)
        else y :: merge(xs, ys1)
    }
    
    val n = xs.length/2
    if (n == 0) 
      xs
    else{
      val (left, right) = xs splitAt n
      merge(msort(less)(left), msort(less)(right))
    }
  } 
}